/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */

package E_implicito_Arvore_Binaria;

import java.util.Vector;

/**
 *
 * @author emanuelle
 */
public class TabelaHash {
    private int tamanhoTabela;
    private Celula celulas[];

    public TabelaHash(int tamanho){
        celulas = new Celula[tamanho];
        this.tamanhoTabela = tamanho;
        for(int i = 0; i < tamanho; i++){ //Preenche a tabela com as células de acordo com o tamanho da tabela hash
            celulas[i] = new Celula(i);
        }
    }

    public Celula getCelula(int posicao){
        return celulas[posicao];
    }

    private int getIndex(int chave){
        return chave % tamanhoTabela;
    }

    public int search(int chave){
        int index = getIndex(chave);
        int acessos = 1;
        int index2 = getIndex(chave/tamanhoTabela);
        if(index2 == 0){
            index2 = 1;
        }
        while(!celulas[index].searchRecord(chave)){
            index = index + index2;
            index = getIndex(index);
            acessos++;
            
        }
        return acessos;

    }

    public int insertion(int chave){
        Record record = new Record(chave);
        int index = getIndex(chave);
        if(celulas[index].insertRecord(record)){ /*******Tenta inserir na posição**********/
            return 0;
        } else { /*Construção e utilização da Arvore Binária de inserção*/
//            int level = 1; /*Nivel da Arvore Binaria*/
//            while(!arvoreInsercao(level, record, index)){
//                level++;
//            }
            arvoreInsercao(record, index); /*ARVORE DINAMICA EM VETOR*/
            return 1;
        }
    }

    public void arvoreInsercao(Record rec, int ind){ /*Arvore em vetor, usando vetor de crescimento dinamico*/
        Vector<Celula> arvore = new Vector();
        Vector<Record> arvRef = new Vector();
        arvore.clear();
        arvRef.clear();
        int posicaoVetor = 1;
        arvore.setSize(posicaoVetor+1);
        arvRef.setSize(posicaoVetor+1);
        arvore.add(posicaoVetor, celulas[ind]);
        int auxInd = ind;
        int auxInd2;
        arvRef.add(posicaoVetor, rec); /*Colocando elemento inserido como referencia do primeiro elemento da arvore*/
        while( arvore.elementAt(posicaoVetor).getRecord() != null) /*Adiciona Celulas a Árvore Binária Completa, com prioridade para a esquerda até achar uma celula vazia. As células guardam o registro que a referenciou para troca.*/
        {
            arvore.setSize((posicaoVetor+1)*2);
            auxInd2 = getIndex(arvRef.get(posicaoVetor).getChave()/tamanhoTabela);
            if(auxInd2 == 0){
                auxInd2 = 1;
            }
            auxInd = arvore.elementAt(posicaoVetor).getPosicao() + auxInd2;
            auxInd = getIndex(auxInd);
            arvRef.add(posicaoVetor*2, arvRef.get(posicaoVetor));
            arvore.add(posicaoVetor*2, celulas[auxInd]);

            auxInd2 = getIndex(arvore.elementAt(posicaoVetor).getRecord().getChave()/tamanhoTabela);
            if(auxInd2 == 0){
                auxInd2 = 1;
            }
            auxInd = arvore.elementAt(posicaoVetor).getPosicao() + auxInd2;
            auxInd = getIndex(auxInd);
            arvRef.add(posicaoVetor*2+1, arvore.elementAt(posicaoVetor).getRecord());
            arvore.add(posicaoVetor*2+1,celulas[auxInd]);
            posicaoVetor++;
        }
        arvore.get(posicaoVetor).insertRecord(arvRef.get(posicaoVetor));

        Record gravado = arvRef.elementAt(posicaoVetor);
        posicaoVetor = (Integer) posicaoVetor/2;

        while(posicaoVetor >= 1){

            if(arvore.elementAt(posicaoVetor).getRecord().getChave() == gravado.getChave()){
                arvore.get(posicaoVetor).setRecord(arvRef.get(posicaoVetor));

                gravado = arvRef.get(posicaoVetor);
            }
            posicaoVetor = (Integer) posicaoVetor/2;
        }

    }


    /*OBS. Arvore construida dinamicamente a cada colisao e para cada nivel, desempenho muito ruim*/
//    private boolean arvoreInsercao(int lev, Record rec, int ind){
//        if(celulas[ind].getRecord()==null){
//            celulas[ind].insertRecord(rec);
//            return true;
//        } else {
//            if(lev>1){
//                int auxIndex = getIndex(rec.getChave()/tamanhoTabela);
//                int index = ind + auxIndex;
//                index = getIndex(index);
//                if(arvoreInsercao(lev-1, rec, index)){ /*Pegando o lado esquerdo da árvore*/
//                    return true;
//                } else{ /*Pegando o lado direito da árvore*/
//                    Record auxRec = celulas[ind].getRecord();
//                    auxIndex = getIndex(auxRec.getChave()/tamanhoTabela);
//                    index = ind + auxIndex;
//                    index = getIndex(index);
//                    if(arvoreInsercao(lev-1, auxRec, index)){ /*Se inserir, inserir o registro que trouxe aqui nesse nó*/
//                        celulas[ind].setRecord(rec);
//                        return true;
//                    } else {
//                        return false;
//                    }
//                }
//            } else {
//                return false;
//            }
//        }
//
//    }

}
